﻿#include "StdAfx.h"
#include "AVLTree.h"

AVLNode* AVLTree::CreateNode(char *a, MyLinkList &ll,int n)
{
	AVLNode *PNode = new AVLNode;
	
	if(PNode == NULL)
		return PNode;
	PNode->_word = a;
	PNode->Bal = 0;
	PNode->count = n;
	PNode->_ml = ll;
	PNode->Pleft = NULL;
	PNode->PRight = NULL;
	return PNode;
}

void AVLTree::Init(TreeAVL &t)
{
	t = NULL;
}


void AVLTree::LeftRotate(TreeAVL &t)
{
	AVLNode *Q;
	Q = t->PRight;
	t->PRight = Q->Pleft;
	Q->Pleft = t;
	t = Q;
}

void AVLTree::LeftBlance(TreeAVL &t)
{
	switch(t->Pleft->Bal)
	{
	case 1:
		RightRotate(t);
		t->Bal = 0;
		t->PRight->Bal =0;
		break;
	case 2:
		LeftRotate(t->Pleft);
		RightRotate(t);
		switch(t->Bal)
		{
		case 0:
			t->Pleft->Bal =0;
			t->PRight->Bal =0;
			break;
		case 1:
			t->Pleft->Bal =0;
			t->PRight->Bal = 2;
			break;
		case 2:
			t->Pleft->Bal = 1;
			t->PRight->Bal = 0;
			break;
		}
		t->Bal =0;
		break;
	}
}


void AVLTree::RightRotate(TreeAVL &t)
{
	AVLNode *Q;
	Q = t->Pleft;
	t->Pleft = Q->PRight;
	Q->PRight = t;
	t = Q;
}

void AVLTree::RightBlance(TreeAVL &t)
{
	switch(t->PRight->Bal)
	{
	case 1:
		RightRotate(t->PRight);
		LeftRotate(t);
		switch(t->Bal)
		{
		case 0:
			t->Pleft->Bal =0;
			t->PRight->Bal =0;
			break;
		case 1:
			t->Pleft->Bal = 0;
			t->PRight->Bal =2;
			break;
		case 2:
			t->Pleft->Bal = 1;
			t->PRight->Bal =0;
			break;
		}
		t->Bal = 0;
		break;
	case 2: 
		LeftRotate(t);
		t->Bal =0;
		t->Pleft->Bal = 0;
		break;

	}
}

int AVLTree::InsertNode(TreeAVL &t,char *c,int _position)
{
	int n=0;
	int res;
	MyLinkList _mll;

	if(t == NULL)
	{
		_mll.InitList();
		t = CreateNode(c,_mll,1);	
		t->_ml.AddNode(_position);
		if(t == NULL)
			return -1;
		return 2;
	}
	else
	{
		if( strcmp(t->_word,c) ==0)
		{
			t->count++;
			t->_ml.AddNode(_position);
			return 0;
		}
		else if(strcmp(t->_word,c) >0)
		{
			
			res = InsertNode(t->Pleft,c,_position);
			if(res < 2)
			{
				return res;
			}
			switch(t->Bal)
			{
			case 0:
				t->Bal = 1;
				return 2;
			case 1:
				LeftBlance(t);
				return 1;
			case 2:
				t->Bal =0;
				return 1;
			}
		}
		else
		{
			res = InsertNode(t->PRight,c,_position);
			if(res <2)
			{
				return res;
			}
			switch(t->Bal)
			{
			case 0:
				t->Bal = 2;
				return 2;
			case 1:
				t->Bal = 0;
				return 1;
			case 2:
				RightBlance(t);
				return 1;
			}
		}
	}

}


void AVLTree::ReplaceString(TreeAVL &t,vector<char*>&aaaa, vector<char*>&_liststring, vector<char*>&_listtring2, ofstream &out)
{
	
	if( t!= NULL)
	{
		ReplaceString(t->Pleft,aaaa,_liststring,_listtring2,out);
		for(int i=0;i<_liststring.size();i++)
		{
			if(strcmp(t->_word,_liststring[i]) ==0)
			{
				Nodelinklist *Pnode = t->_ml.ml.Phead;
				while(Pnode != NULL)
				{
					aaaa[Pnode->data] = _listtring2[i];
					Pnode = Pnode->Pnext;
				}
			}
			
		}
		ReplaceString(t->PRight,aaaa,_liststring,_listtring2,out);
	}



}

void AVLTree::RNL(TreeAVL &t, ofstream &out)
{
	if(t != NULL)
	{
		RNL(t->Pleft,out);
		out<<t->_word<<"    so lan xuat hien "<<t->count<<"vi tri xuat hien";

		Nodelinklist *Node = t->_ml.ml.Phead;
		while(Node)
		{
			out<<" "<<Node->data<<"";
			Node = Node->Pnext;
		}
		out<<endl;
		RNL(t->PRight,out);
	}
	
}

AVLTree::AVLTree(void)
{

}


AVLTree::~AVLTree(void)
{
}
